package cpagraph;

import java.util.Vector;
//import javax.microedition.rms.*;


public class Graph
{
	/**
	 * list of nodes added to the graph.
	 */
	public Vector<Node> nodes;
	
	/**
	 * Initializes new graph object.
	 * Add nodes using method addNode(). 
	 */
	public Graph()
	{
		nodes = new Vector<Node>();
	}
	
	/**
	 * Adds new node to the graph's list of nodes.
	 * To connect it to other nodes of the graph,
	 * use method connectNodes().
	 * 
	 * @param n node to be added to graph
	 */
	public void addNode(Node n)
	{
		nodes.addElement(n);
	}
	
	/**
	 * If a is connected to n and n is connected to b,
	 * this method adds a new Edge connecting a and b
	 * with weight w(a, n) + w(n, b).
	 * This method is mainly used in deleteNode2().
	 * 
	 * @param a starting node
	 * @param n by-passed node in the middle
	 * @param b ending node
	 */
	public void addTransition(Node a, Node n, Node b)
	{
		if (a.isAdjacentTo(n) && n.isAdjacentTo(b))
		{
			double newWeight = a.getEdge(n).weight + n.getEdge(b).weight;
			
			connectNodes(a, b, newWeight);
		}
	}
	
	/**
	 * Returns true, if a path (a,b,c) exists,
	 * such that at least one busline travels along this path.
	 * 
	 * @param a node, where node b is adjacent
	 * @param b node with adjacents a and c
	 * @param c node, where node b is adjacent
	 * @return true, if the is a bus going from a to b to c, false if there is no such bus
	 */
	public boolean isBusTraversing(Node a, Node b, Node c)
	{
		Edge ab = a.getEdge(b);
		Edge bc = b.getEdge(c);
		if ((ab == null) || (bc == null))
			return false;
		
		for (int i = 0; i < a.busses.size(); i++)
		{
			Bus bus = a.busses.elementAt(i);
			if (b.isAssignedTo(bus) && c.isAssignedTo(bus))
			{
				return true;
			}
		}
		
		return false;
	}
	
	/**
	 * Searches graph for node by given id.
	 * 
	 * @param id node's ID to be searched for
	 * @return node with given id, null if it doesn't exist
	 */
	public Node findNodeByID(String id)
	{
		for (int i = 0; i < nodes.size(); i++)
		{
			Node n = nodes.elementAt(i);
			
			if (n.osmNode.id.equals(id))
				return n;
		}
		
		return null;
	}
	
	/**
	 * @param a Node tested to be connected with node b
	 * @param b Node tested to be connected with node a
	 * @return true, if a is adjacent to b and b is adjacent to a, false otherwise.
	 */
	public boolean areConnected(Node a, Node b)
	{
		return a.isAdjacentTo(b) && b.isAdjacentTo(a);
	}
	
	/**
	 * If nodes a and b are not connected yet, a new edge with weight w is created
	 * and added to both nodes lists of incidents.
	 * The lists of adjacent nodes of each node is also updated.
	 * 
	 * @param a Node to be connected with node b
	 * @param b Node to be connected with node a
	 * @param w Weight to be assigned to new introduced edge between nodes a and b
	 */
	public void connectNodes(Node a, Node b, double w)
	{
		if (!areConnected(a, b))
		{
			Edge e = new Edge(a, b, w);
			
			a.incidents.addElement(e);
			a.adjacents.addElement(b);
			b.incidents.addElement(e);
			b.adjacents.addElement(a);
		}
	}
	
	/**
	 * Same as connectNodes(a, b, w)
	 * 
	 * @param a Node to be connected with node b
	 * @param b Node to be connected with node a
	 * @param w Weight to be assigned to new introduced edge between nodes a and b
	 */
	public void addEdge(Node a, Node b, double w)
	{
		if (!areConnected(a, b))
		{
			Edge e = new Edge(a, b, w);
			
			a.incidents.addElement(e);
			a.adjacents.addElement(b);
			b.incidents.addElement(e);
			b.adjacents.addElement(a);
		}
	}
	
	/**
	 * Removes edge (a, b) from the node's list of incident edges,
	 * removes node a from b's list of adjacents and vice versa.
	 * 
	 * @param a Ending node of the edge to be deleted
	 * @param b Ending node of the edge to be deleted
	 */
	public void disconnectNodes(Node a, Node b)
	{
		Edge e = a.getEdge(b);
		
		a.incidents.removeElement(e);
		a.adjacents.removeElement(b);
		b.incidents.removeElement(e);
		b.adjacents.removeElement(a);
	}
	
	/**
	 * deleteNode2() disconnects a node from its adjacents
	 * and removes it from the list of nodes of the graph.
	 * It only introduces new edges between nodes a b from the list of adjacents,
	 * if there exists a busline going from node a to b via the node to be deleted.
	 * 
	 * @param n Node to delete from graph
	 */
	public void deleteNode2(Node n)
	{
		for (int i = n.adjacents.size() - 1; i >= 0; i--)
		{
			Node a = n.adjacents.elementAt(i);
			for (int k = 0; k < i; k++)
			{
				Node b = n.adjacents.elementAt(k);
				
				if (isBusTraversing(a, n, b))
				{
					addTransition(a, n, b);
				}
			}
			
			disconnectNodes(a, n);
		}
		
		if (!nodes.removeElement(n))
		{
			System.out.print("Node " + n.osmNode.id + " has been disconnected, but could not be removed.");
		}
	}
	
	public Vector<String> busStopsToRecords()
	{
		Vector<String> stops = new Vector<String>();
		
		for (int i = 0; i < nodes.size(); i++)
		{
			Node stop = nodes.elementAt(i);
			
			stops.add(stop.toRecord());
		}
		
		return stops;
	}
	
	/**
	 * The output of this method can be written to a file,
	 * using RMS.
	 * The two first entries in a row are indices to nodes from the graph's list of nodes.
	 * The third and every following entry are the numbers of the busses going from one node to the other.
	 * 
	 * @return vector of strings, each strings represents an edge of the graph
	 */
	public Vector<String> toRecords()
	{
		Vector<String> records = new Vector<String>();
		
		Vector<String> skipEdges = new Vector<String>();
		for (int i = 0; i < nodes.size(); i++)
		{
			Node a = nodes.elementAt(i);
			
			for (int k = 0; k < a.adjacents.size(); k++)
			{
				Node b = a.adjacents.elementAt(k);
				
				if ( skipEdges.contains(a.osmNode.id+b.osmNode.id)
						|| skipEdges.contains(b.osmNode.id+a.osmNode.id))
					continue;
				
				String edgeFormat = Integer.toString(i);
				edgeFormat += " " + Integer.toString(nodes.indexOf(b));
				
				Edge edge = a.getEdge(b);
				
				Vector<Bus> busses = edge.assignedTo();
				for (int j = 0; j < busses.size(); j++)
				{
					edgeFormat += " " + busses.elementAt(j).number;
				}
				
				records.add(edgeFormat);
				skipEdges.add(a.osmNode.id + b.osmNode.id);
			}
		}
		
		return records;
	}
	
	/**
	 * Deletes node from graph by removing from nodelist
	 * and disconnecting from any adjacent node.
	 * Repairs graph by connecting all adjacent nodes with each other.
	 * Please use newer deleting method deleteNode2() instead.
	 * 
	 * @param n Node to be deleted
	 */
	@Deprecated
	public void deleteNode(Node n)
	{
		{
			for (int i = 0; i < n.adjacents.size(); i++)
			{
				Node a = n.adjacents.elementAt(i);
				for (int k = i + 1; k < n.adjacents.size(); k++)
				{
					Node b = n.adjacents.elementAt(k);
					
					if (a.equals(b))
						System.out.println("two identical adjacent nodes detected! id=" + n.osmNode.id);
					if (a==b)
						System.out.println("---> a==b, references are equal.");
					
					double newWeight = a.getEdge(n).weight + b.getEdge(n).weight;
					
					connectNodes(a, b, newWeight);
				}
				disconnectNodes(a, n);
			}
			//System.out.println("Node id=" + n.osmNode.id + " deleted.");
			if (!nodes.removeElement(n))
			{
				System.out.print("could not remove node id=" + n.osmNode.id);
				System.out.println(" from list of nodes, but disconnected and removed 2 edges replaced by new one.");
			}
		}
	}
}
